package com.breeze.tree;

/**
 * 二叉排序树(二叉搜索树，也称为二叉查找树)
 */
public class BinarySortTree {
    Node root;

    /**
     * 添加数据,按照左轻右重原则添加.
     *
     * @param value
     */
    public void addData(int value) {
        Node node = new Node(value);
        if (root == null) {
            root = node;
            return;
        }
        Node parent = findParentNode(root, node);
        if (node.value > parent.value) {
            parent.right = node;
        } else {
            parent.left = node;
        }
    }

    /**
     * 查找给定结点的父结点
     *
     * @param r       当前子树的顶层结点
     * @param newNode 要查找的结点
     * @return 返回要查找的结点的父结点
     */
    private static Node findParentNode(Node r, Node newNode) {
        if (newNode.value > r.value) {
            if (r.right == null) {
                return r;
            } else {
                return findParentNode(r.right, newNode);
            }
        } else {
            if (r.left == null) {
                return r;
            } else {
                return findParentNode(r.left, newNode);
            }
        }
    }

    /**
     * 中序遍历(递归)，为了可以从小到达输出
     */
    public void showMiddleOrder() {
        if (root == null) {
            return;
        }
        middleOrder(root);
    }

    private void middleOrder(Node node) {
        if (node == null) {
            return;
        }
        middleOrder(node.left);
        System.out.print(node.value + ",");
        middleOrder(node.right);
    }

    class Node {
        int value;
        Node left, right;

        public Node(int value) {
            this.value = value;
        }
    }
}
